


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

public class Ejercicio3Viejo {
	
	public String fileNameIn = "/home/chudi/workspace/algo32009vamosaverquesale/algo3/TP1/src/Tp1Ej3_azar_500.in";
	public String fileNameOut = "/home/chudi/workspace/algo32009vamosaverquesale/algo3/TP1/src/Tp1Ej3_azar_500.out";

	
	public static final String horizontal = "horizontal";
	public static final String vertical = "vertical";
	private static int cantSolPorComponente = 0;
	
	public enum TipoPieza {horizontal, vertical};
	
	private static Integer cantSol = 1; 
	private static Integer cantLibres = 0;
	private static Integer[][] tablero;
	
	private static int casillerosSinPintarFill;
	
	private static ArrayList<ComponenteConex> listComConex;
	
	private static boolean tengoUnaComponenteMala = false;
	

	/**
	 * @param args
	 */
	
	public void leeteElArchivo() throws Exception {

		BufferedWriter bw = null;
		bw = new BufferedWriter(new FileWriter(new File(fileNameOut)));
		
		BufferedReader br = null;
		br = new BufferedReader(new FileReader(new File(fileNameIn)));
		String linea = br.readLine();
		Integer cantidad_filas = Integer.parseInt(linea);
		while (cantidad_filas != -1) {
			long init = System.nanoTime();
			tablero = new Integer [cantidad_filas][cantidad_filas];
			cantLibres = 0;
			cantSol = 1;
			String lineaString = br.readLine();
			
			for(int i = 0 ; i < cantidad_filas; i++) {
				for(int j = 0 ; j < cantidad_filas ; j++) {
					char caracter = lineaString.charAt(j);
					if(caracter == '_') {
						tablero[i][j] = -1;
					} else {
						tablero[i][j] = 0;
						cantLibres++;
					}
				}
				lineaString = br.readLine();
			}
			
// Busca componentes conexas del algoritmo		
			listComConex = new ArrayList<ComponenteConex>();
			Integer[] newXY = buscarProximaUbicacion(0, 0, 0, 0);
			int colorReemplazo = 10;
			casillerosSinPintarFill = cantLibres;
			while(casillerosSinPintarFill > 0){
				newXY = buscarProximaUbicacion(0, 0, 0, 0);
				ComponenteConex compConexa = new ComponenteConex(colorReemplazo,newXY);				
				floodFill(newXY[0], newXY[1], 0, colorReemplazo,compConexa);
				
				//Checkea podas sobre las componentes, si es mala, sale de este while y setea la global tengoUnaComponenteMala en true
				if (checkearComponenteConexa(compConexa)){
					break; 
				}
				
				listComConex.add(compConexa);
				colorReemplazo += 2;
			}
			
			imprimirSol();
			
			if(!tengoUnaComponenteMala){
				Collections.sort(listComConex);

				Iterator<ComponenteConex> it = listComConex.iterator();
				while (it.hasNext() && !tengoUnaComponenteMala) {
//					System.out.println("-Compo conex start-----------------------------------------------------------------");
					ComponenteConex componente = (ComponenteConex) it.next();
					ponerObligatorias(componente);
					if(componente.cantidad == 0){
						it.remove();
//						System.out.println("-Compo conex removed-----------------------------------------------------------------");
					}
//					System.out.println("-Compo conex end-----------------------------------------------------------------");
				}
				
//				System.out.println("-----Begin bag Tracking------------------------------------------");
				
				//ACA ES EL BAG TRaking
				Iterator<ComponenteConex> it2 = listComConex.iterator();
				while (it2.hasNext() && !tengoUnaComponenteMala) {
					ComponenteConex componente = (ComponenteConex) it2.next();
					
					newXY = buscarProximaUbicacion(componente.nodoInit[0],componente.nodoInit[1], componente.color, componente.color+1);
					cantSolPorComponente = 0;
					cantLibres = componente.cantidad;
//					System.out.println("-----Begin tapar hor1------------------------------------------");
					tapar(newXY[0], newXY[1], TipoPieza.horizontal, componente.color, componente.color+1 );
//					System.out.println("-----Begin tapar ver2------------------------------------------");
					tapar(newXY[0], newXY[1], TipoPieza.vertical, componente.color, componente.color+1);
					
					tengoUnaComponenteMala = cantSolPorComponente == 0;
					cantSol *= cantSolPorComponente;
				}
				
			}

			System.out.println(cantidad_filas * cantidad_filas + " " + (System.nanoTime() - init));
			if(tengoUnaComponenteMala){
				bw.append("0");
			}else{
				bw.append(cantSol.toString());
			}
			bw.newLine();
			tengoUnaComponenteMala = false;
			listComConex.clear();
			cantidad_filas = Integer.parseInt(lineaString);
		}
		br.close();
		bw.close();
	}

	/**
	 * Checkea el tablero y pone todas las veces necesarias las piezas obligatorias por cada componente conexa
	 * @param componente
	 */
	private static void ponerObligatorias(ComponenteConex componente) {
		Integer[] newXY = componente.nodoInit;

		while( newXY != null && !tengoUnaComponenteMala){
			if(pongoObligatoria(newXY, componente.color, componente.color+1)){
				componente.cantidad -=2;
				cantLibres -=2;
				newXY = componente.nodoInit; // Vuelvo atras a la coordenada inicial, porque ya puse en este ciclo
			}
			newXY = buscarProximaUbicacion(newXY[0], newXY[1] + 1, componente.color, componente.color+1);
		}
		
	}

	/***
	 * Pone una pieza obligatoria en el lugar XY, mira alrededor y si encuentra mas de una opcion, devuelve falso, sino pone la ficha
	 * @param newXY
	 * @param color1
	 * @param color2
	 * @return
	 */
	private static boolean pongoObligatoria(Integer[] newXY, int color1, int color2) {

		int contadorCasillerosLibresAlrededor = 0;
		Integer fila = newXY[0];
		Integer col = newXY[1];
		
		TipoPieza tipoPieza = null;
		Integer filaCand = null;
		Integer colCand = null;
		
		if(fila - 1 >= 0 && (tablero[fila-1][col].equals(color1) || tablero[fila-1][col].equals(color2)) ){
			contadorCasillerosLibresAlrededor++;
			filaCand = fila - 1  ;
			colCand = col;
			tipoPieza = TipoPieza.vertical;
		}
		
		if( fila+1 < tablero.length && (tablero[fila+1][col].equals(color1) || tablero[fila+1][col].equals(color2)) ){
			contadorCasillerosLibresAlrededor++;
			filaCand = fila; // Ajusto la filaCandidato, para poner la ficha
			colCand = col;
			tipoPieza = TipoPieza.vertical;
		}
		
		if( col - 1 >= 0 && (tablero[fila][col - 1].equals(color1) || tablero[fila][col - 1].equals(color2)) ){
			contadorCasillerosLibresAlrededor++;
			filaCand = fila;
			colCand = col - 1;
			tipoPieza = TipoPieza.horizontal;
		}
		
		if( col + 1 < tablero.length && (tablero[fila][col + 1].equals(color1) || tablero[fila][col + 1].equals(color2)) ){
			contadorCasillerosLibresAlrededor++;
			filaCand = fila;
			colCand = col; // Ajusto la colCandidato, para poner la ficha
			tipoPieza = TipoPieza.horizontal;
		}
		
		if(contadorCasillerosLibresAlrededor > 1){
			return false;
		}

		if( tipoPieza == null){ 
			tengoUnaComponenteMala = true;
			return false;
		}
//		|| !puedoPonerPieza(fila, col, tipoPieza, color1, color2 ) ) {
		
		ponerPieza(filaCand, colCand, tipoPieza);
		
		imprimirSol();
		tengoUnaComponenteMala = puedoPodar(filaCand, colCand, tipoPieza, color1, color2);
		return true;
	}

	private static boolean checkearComponenteConexa(ComponenteConex compConexa) {
		if( (compConexa.blancos != compConexa.negros) || (compConexa.cantidad % 2 != 0)){
			tengoUnaComponenteMala = true;
			return tengoUnaComponenteMala;
		}
		tengoUnaComponenteMala = false;
		return tengoUnaComponenteMala;
	}

	private static void floodFill(Integer x, Integer y, int colorObj, int colorReemplazo, ComponenteConex compConexa) {
		if( x == tablero.length || y == tablero.length || x < 0 || y < 0){
			return;
		}
		if (tablero[x][y] != colorObj) {
			return;
		}
		
		if (tablero[x][y] == colorReemplazo) {
			return;
		}
		
		compConexa.cantidad += 1;
		casillerosSinPintarFill--;
		
		if(colorReemplazo % 2 == 0){//Blancos es par
			compConexa.blancos++;
			colorReemplazo++;
		} else {
			compConexa.negros++;
			colorReemplazo--;
		}
		tablero[x][y] = colorReemplazo;
		
		floodFill(x - 1, y, colorObj, colorReemplazo,compConexa);
		floodFill(x + 1, y, colorObj, colorReemplazo,compConexa);
		floodFill(x, y - 1, colorObj, colorReemplazo,compConexa);
		floodFill(x, y + 1, colorObj, colorReemplazo,compConexa);
	}

	public static void tapar(Integer fila, Integer col, TipoPieza tipoPieza, int color1, int color2) {
//		System.out.println("--- antes puedo poner pieza ---");
		if( !puedoPonerPieza(fila, col, tipoPieza, color1, color2 ) ) {
//			System.out.println("--- no puedo poner pieza ---");
			return;
		}
//		System.out.println("--- despues puedo poner pieza ---");
		
		ponerPieza(fila, col, tipoPieza);
		cantLibres--;
		cantLibres--;
		
//		System.out.println(cantLibres);
		boolean poda = false;
		if(fila<tablero.length && col < tablero.length && puedoPodar(fila, col, tipoPieza, color1, color2)) {
			poda = true;
		}
		
		Integer[] newXY = buscarProximaUbicacion(fila, col, color1, color2);
		
		imprimirSol();
		if(cantLibres.equals(0)) {
			cantSolPorComponente++;
		} else if (poda){
			;
		}else{	
			tapar(newXY[0], newXY[1], TipoPieza.horizontal, color1, color2);
			tapar(newXY[0], newXY[1], TipoPieza.vertical, color1, color2);
		}
		
		sacarPieza(fila, col, tipoPieza, color1, color2);
		cantLibres++;
		cantLibres++;
		imprimirSol();
		
	}

	private static boolean puedoPodar(Integer fila, Integer col, TipoPieza tipoPieza, int color1, int color2) {
		if(tipoPieza.equals(TipoPieza.horizontal)) {
			
//			System.out.println("col: " + col);
//			System.out.println("fil: " + fila);
			
//			System.out.println("poda1");
			if(fila+1 < tablero.length && (tablero[fila+1][col].equals(color1) || tablero[fila+1][col].equals(color2)) ){
//				System.out.println("entre por 1");
				if(!chequearDeAbajo(fila+1,col,color1,color2) ){
					return true;
				}			
			}
			
//			System.out.println("poda2");
			if(fila+1 < tablero.length && col+1 < tablero.length && (tablero[fila+1][col+1].equals(color1) || tablero[fila+1][col+1].equals(color2))){
//				System.out.println("entre por 2");
				if(!chequearDeAbajo(fila+1,col+1,color1,color2)){
					return true;
				}
			}
			
		}else {
//			System.out.println("poda3");
			if(fila+1 < tablero.length && col-1 >= 0 && (tablero[fila+1][col-1].equals(color1) || tablero[fila+1][col-1].equals(color2))){
				if(!chequearDeAbajo(fila+1,col-1,color1,color2)){
					return true;
				}			
			}
			
//			System.out.println("poda4");
			if(fila+2 < tablero.length &&  (tablero[fila+2][col].equals(color1) || tablero[fila+2][col].equals(color2))){
				if(!chequearDeAbajo(fila+2,col,color1,color2)){
					return true;
				}
			}
//			System.out.println("poda5");
			if(fila+1 < tablero.length && col+1 < tablero.length  && (tablero[fila+1][col+1].equals(color1) || tablero[fila+1][col+1].equals(color2))){
				if(!chequearDeAbajo(fila+1,col+1,color1,color2) ){
					return true;
				}			
			}
		}
//		System.out.println("no pode");
		return false;
	}

	private static boolean chequearDeAbajo(int i, int j, int color1, int color2) {
		
		boolean chequeo = false;
	
		if(i+1<tablero.length && j < tablero.length && (tablero [i+1][j].equals(color1) || tablero [i+1][j].equals(color2)) ){
			chequeo |= true;
		}
		
		if(i<tablero.length && j+1 < tablero.length && (tablero [i][j+1].equals(color1) || tablero [i][j+1].equals(color2)) ){
			chequeo |= true;
		}
		
		if(i<tablero.length && j-1 >= 0 && ( tablero [i][j-1].equals(color1) || tablero [i][j-1].equals(color2))){
			chequeo |= true;
		}
		
		if(i-1 >= 0 && j < tablero.length && (tablero [i-1][j].equals(color1) || tablero [i-1][j].equals(color2))){
			chequeo |= true;
		}
		
		return chequeo;
	}

	private static void imprimirSol() {
//		String newLine = System.getProperty("line.separator");
//		StringBuffer sb = new StringBuffer();
//		for (int i = 0; i < tablero.length; i++) {
//			for (int j = 0; j < tablero.length; j++) {
//				if(tablero[i][j] == 1) {
//						sb.append("== ");
//				} else if(tablero[i][j] == 2) {
//					sb.append("|| ");
//			    } else if(tablero[i][j] == -1) {
//					sb.append(".. ");
//			    } else if(tablero[i][j] == 0) {
//					sb.append("VV ");
//			    } else {
//			    	sb.append(tablero[i][j] + " ");
//			    }
//			}
//			sb.append(newLine);
//		}
//		System.out.println(sb.toString());
//		System.out.println(newLine);
	}

	private static void sacarPieza(Integer filaAnterior, Integer colAnterior, TipoPieza tipoPieza, int color1, int color2) {
		if(tipoPieza.equals(TipoPieza.horizontal)) {
			tablero[filaAnterior][colAnterior] = color1;
			tablero[filaAnterior] [colAnterior +1] = color2;
		} else {
			tablero[filaAnterior][colAnterior] = color1;
			tablero[filaAnterior + 1] [colAnterior] = color2;
		}
	}

	private static Integer[] buscarProximaUbicacion(Integer fila, Integer col, int color1, int color2) {
		Integer[] res = new Integer[2];
		for (; fila < tablero.length; fila++) {
			for (; col < tablero.length; col++) {
				if(tablero[fila][col].equals( color1 ) || tablero[fila][col].equals( color2 )) {
					res[0] = fila;
					res[1] = col;
					return res;
				}
			}
			col = 0;
		}
		return null;
	}

	private static void ponerPieza(Integer fila, Integer col, TipoPieza tipoPieza) {
		if(tipoPieza.equals(TipoPieza.horizontal)) {
			tablero[fila][col] = 1;
			tablero[fila] [col +1] = 1;
		} else {
			tablero[fila][col] = 2;
			tablero[fila + 1] [col] = 2;
		}
		
	}

	private static boolean puedoPonerPieza(Integer fila, Integer col, TipoPieza tipoPieza, int color1, int color2) {
		
		if(tipoPieza.equals(TipoPieza.horizontal)) {
			if(col.equals(tablero.length - 1)) {
				return false;
			} 
			
			if((tablero[fila][col].equals(color1)|| tablero[fila][col].equals(color2))&& (tablero[fila][col + 1].equals(color1)|| tablero[fila][col + 1].equals(color2))) {
				return true;
			} else {
				return false;
			}
			
		} else {
			if(fila.equals(tablero.length - 1)) {
				return false;
			} 
			
			if((tablero[fila][col].equals(color1)|| tablero[fila][col].equals(color2)) && (tablero[fila + 1][col].equals(color1)|| tablero[fila + 1][col].equals(color2))) {
				return true;
			} else {
				return false;
			}
		}
	}

	public static void main(String[] args) {
		if (args.length > 0){
//			fileNameIn = args[0];
		}
		
		try {
			Ejercicio3Viejo test = new Ejercicio3Viejo();
			if (args.length > 0){
				test.fileNameIn = args[0];
			}
			
			test.leeteElArchivo();
		} catch (Exception e) {
			e.printStackTrace();
		}

	}
	


}
